COMMENT ⊗   VALID 00007 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	% Fonts for Digital Halftones, to be submitted to TUGboat
C00005 00003	\leftline{\bf Fonts for Digital Halftones}
C00017 00004	My next attempt was to look at halftone pictures in books and newspapers,
C00029 00005	We can also create an analogous font |hf723| for the high-resolution APS,
C00032 00006	\medbreak Let's turn now to another problem: Suppose we have an image for which
C00037 00007	\message{Now say "tex end" to get the rest!}
C00038 ENDMK
C⊗;
% Fonts for Digital Halftones, to be submitted to TUGboat
% (this version assumes that \hsize=6.5in!)

\font\logo=manfnt \def\MF{{\logo META}\-{\logo FONT}}
\font\tilt=tcmr10
\font\dith=dt300[hf,dek]
\font\dott=dot300[hf,dek]

\newif\ifaps % are we making copy for the APS?
%\apsfalse
\apstrue

\newcount\n
\def\tbox#1{\hidewidth\vbox to1.5em{\offinterlineskip\tilt
 \vfil\expandafter\tb\number#1\empty\tb\vfil}\hidewidth}
\def\tb#1#2\tb{\ifx#1\empty\else\tb#2\tb\hbox{#1}\fi}

\def\mbox#1{$\vcenter{\kern-.2pt\hrule\kern-.2pt
 \hbox to12pt{\kern-.2pt\vrule height 9pt depth 3pt\hss#1\hss\vrule\kern-.2pt}
 \kern-.2pt\hrule\kern-.2pt}$}
\def\bbox{$\vcenter{\hbox to12pt{\vrule height 9pt width0pt depth 3pt\hss}
 \kern-.2pt\hrule\kern-.2pt}$}
\def\lbox{$\vcenter{\hbox to12pt{\kern-.2pt\vrule height 9pt depth 3pt\hss}}$}

\chardef\other=12
\def\ttverbatim{\begingroup
  \catcode`\\=\other \catcode`\{=\other \catcode`\}=\other
  \catcode`\$=\other \catcode`\&=\other \catcode`\#=\other
  \catcode`\%=\other \catcode`\~=\other \catcode`\↑=\other
  \catcode`\_=\other
  \obeyspaces \obeylines \tt}
{\obeyspaces\gdef {\ }}
\catcode`\|=\active \def|{\ttverbatim\let|=\endgroup}
\def\beginlines{\par\begingroup\nobreak\medskip\parindent=0pt \obeylines
  \hrule\kern1pt\nobreak \everypar{\strut}}
\def\endlines{\kern1pt\hrule\endgroup\medbreak\noindent}

\leftline{\bf Fonts for Digital Halftones}
\medskip
\leftline{\indent Donald E. Knuth}
\leftline{\indent Stanford University}
\bigskip
\noindent
Small pictures can be ``typeset'' on raster devices in a way that simulates
the screens used to print fine books on photography. The purpose of this note
is to discuss some experiments in which \MF\ has created fonts
from which halftones can be generated easily on laser printers. High levels
of quality are not possible at low resolution, and large pictures will overflow
\TeX's memory at high resolution; yet these fonts have proved to be useful
in several applications, and their design involves a number of interesting
issues.

I began this investigation several years ago when about a dozen of Stanford's
grad students were working on a project to create ``high-tech self-portraits''
[see Ramsey Haddad and Donald E. Knuth, ``A programming and problem-solving
seminar,'' {\sl Stanford Computer Science Report 1055\/}
(Stanford, California, June 1985), pp.~88--103].
The students were manipulating digitized graphic images in many ingenious ways,
but Stanford had no output devices by which the computed images could be
converted to hardcopy. Therefore I decided to create a font by which
halftones could be produced using \TeX.

Such a font is necessarily device-dependent. For example, a laser printer with
300 pixels per inch cannot mimic the behavior of another with 240 pixels per
inch, if we are trying to control the patterns of pixels. I~decided to use our
300-per-inch Imagen laserprinter because it gave better control over
pixel quality than any other machine we had.

It seemed best at first to design a font whose ``characters'' were
tiny $8\times8$ squares of pixels. The idea was to have 65 characters
for 65 different levels of brightness: For $0\le k\le64$ there would be
one character with exactly $k$ black pixels and $64-k$ white pixels.

Indeed, it seemed best to find some permutation $p$ of the 64 pixels in an
$8\times8$ square so that the black pixels of character~$k$ would be
$p_0$, $p_1$, \dots,~$p_{k-1}$. My first instinct was to try to
keep positions $p_0$, $p_1$, $p_2$,~\dots\ as far apart from each other
as possible. So my first \MF\ program painted pixels black by ordering
the positions as follows:
$$\vbox{\halign{&\mbox{#}\cr
45&29&34&18&46&30&33&17\cr
13&61&2&50&14&62&1&49\cr
39&23&40&24&36&20&43&27\cr
7&55&8&56&4&52&11&59\cr
47&31&32&16&44&28&35&19\cr
15&63&0&48&12&60&3&51\cr
37&21&42&26&38&22&41&25\cr
5&53&10&58&6&54&9&57\cr}}$$
[This is essentially the ``ordered dither'' matrix of B. E. Bayer; see the survey
paper by Jarvis, Judice, and Ninke in {\sl Computer Graphics and Image
Processing\/ \bf5} (1976), 22--27.]

It turns out to be easy to create such a font with \MF:
\beginlines
|% halftone font with 65 levels of gray, characters "0" (white) to "p" (black)|
\smallskip
|pair p[]; % the pixels in order (first p0 becomes black, then p1, etc.)|
|pair d[]; d[0]=(0,0); d[1]=(1,1); d[2]=(0,1); d[3]=(1,0); % dither control|
|def wrap(expr z)=(xpart z mod 8,ypart z mod 8) enddef;|
|for i=0 upto 3: for j=0 upto 3: for k=0 upto 3:|
| p[16i+4j+k]=wrap(4d[k]+2d[j]+d[i]+(2,2)); endfor endfor endfor|
\smallbreak
|w#:=8/pt; % that's 8 pixels|
|font_quad:=w#; designsize:=8w#;|
\smallbreak
|picture prevchar; prevchar=nullpicture; % the pixels blackened so far|
|for i=0 upto 64:|
| beginchar(i+ASCII"0",w#,w#,0); currentpicture:=prevchar;|
| if i>0: addto currentpicture also unitpixel shifted p[i-1]; fi|
| prevchar:=currentpicture; endchar;|
| endfor|
\endlines
This file was called |dt.mf|; I used it to make a font called `|dt300|'
by applying \MF\ in the usual way to the following file |dt300.mf|:
\beginlines
|% Halftone font for Imagen, dithered|
|mode_setup;|
|if (pixels_per_inch<>300) or (mag<>1):|
| errmessage "Sorry, this font is only for resolution 300";|
| errmessage "Abort the run now or you'll clobber the TFM file";|
| forever: endfor|
|else: input dt fi|
|end.|
\endlines
(The purpose of |dt300.mf| is to enforce the device-dependence of this font.)

It's fairly easy to typeset pictures with |dt300| if you input the
following macro file |hf65.tex| in a \TeX\ document:
\beginlines
|\font\halftone=dt300  % for halftones on the Imagen 300|
|\chardef\other=12|
\smallskip
|\def\beginhalftone{\vbox\bgroup\offinterlineskip\halftone|
| \catcode`\\=\other \catcode`\↑=\other \catcode`\_=\other|
| \catcode`\.=\active \starthalftone}|
|{\catcode`\.=\active \catcode`\/=0 \catcode`\\=\other|
| /gdef/starthalftone#1\endhalftone{/let.=/endhalftoneline|
|  /beginhalftoneline#1/endhalftone}}|
|\def\beginhalftoneline{\hbox\bgroup\ignorespaces}|
|\def\endhalftoneline{\egroup\beginhalftoneline}|
|\def\endhalftone{\egroup\setbox0=\lastbox\unskip\egroup}|
\smallbreak
|% Example of use:|
|% \beginhalftone|
|% chars for top line of picture.|
|% chars for second line of picture.|
|% ...|
|% chars for bottom line of picture.|
|% \endhalftone|
\endlines
(These macros are a bit tricky because `|\|' is one of the legal
characters in |dt300|; we must make backslashes revert temporarily
to the status of ordinary symbols.)

Unfortunately, the results with |dt300| weren't very good. For example,
here are three typical pictures, shown full size as they came off
the machine:\footnote*{Asterisks are used throughout this paper to denote
places where output from the 300-pixels-per-inch Imagen printer has been
pasted in.  Elsewhere, the typesetting is by an APS Micro-5, which has a
resolution of about 723 pixels per inch.}
$$\vbox to 44mm{}$$ % generated by fig1.tex
The squareness of the pixels is much too prominent.

Moreover, the laser printer does strange things when it is given
pixel patterns like those in |dt300|:*
\bigskip
\ifaps\setbox8=\fi\centerline{\n=0
 \loop\vbox{\offinterlineskip
  \halign{&\hfil##\hfil\cr \ifodd\n\else\tbox\n\fi\cr
   \advance\n by`0 \dith\char\n\char\n\char\n\cr
   \advance\n by`0 \dith\char\n\char\n\char\n\cr
   \advance\n by`0 \dith\char\n\char\n\char\n\cr
   \advance\n by`0 \dith\char\n\char\n\char\n\cr
   \advance\n by`0 \dith\char\n\char\n\char\n\cr
   \advance\n by`0 \dith\char\n\char\n\char\n\cr
   \advance\n by`0 \dith\char\n\char\n\char\n\cr
   \advance\n by`0 \dith\char\n\char\n\char\n\cr}}%
 \ifnum\n<64 \advance\n by 1 \repeat}
\ifaps\setbox6=\vbox{} \ht6=\ht8 \wd6=\wd8 \dp6=\dp8 \box6 \setbox8=\null\fi
\bigskip\noindent
Although character $k$ has more black pixels than character $k-1$, the
characters do not increase their darkness monotonically! Character~6
seems darker than character~7; this is an optical illusion. Character~32
is darker than many of the characters that follow, and in this case
the effect is not illusory: Examination with a magnifying glass shows
that the machine deposits its toner
in a very curious fashion.

Another defect of this approach is that most of the
characters are quite dark; 50\% density is reached already at about
character number~16. Hence |dt300| overemphasizes light tones.

My next attempt was to look at halftone pictures in books and newspapers,
in order to discover the secret of their success. Aha! These were done
by making bigger and bigger black dots; in other words, the order of pixels
$p_0$, $p_1$, \dots\ was designed to keep black pixels {\it close together\/}
instead of far apart. Also, the dots usually appear in a grid that has
been rotated $45↑\circ$, since human eyes don't notice the dottiness
at this angle as much as they do when a grid is rectilinear. Therefore
I decided to blacken pixels in the following order:
$$\def\\{\omit\hfil}\def\|{\omit\lbox}\def\_{\omit\bbox}
\vbox{\halign{&\mbox{#}\cr
\\&\\&\\&\\&\\&\\&\\&63\cr
\\&\\&\_&\_&\_&\_&39&47&55\cr
\\&\\&\|&\\&\\&\\&28&15&23&31&35\cr
\\&\\&\|&\\&\\&52&20&4&7&11&43&59\cr
\\&\\&\|&62&60&44&12&1&3&19&51\cr
\\&\\&38&46&54&36&25&17&9&27\cr
\\&\\&29&14&22&30&34&49&41&33\cr
\\&53&21&5&6&10&42&58&57&\\&\|\cr
61&45&13&0&2&18&50&\\&\\&\\&\|\cr
\\&37&24&16&8&26&\_&\_&\_&\_&\|\cr
\\&\\&\\&48&40&32\cr
\\&\\&\\&\\&56\cr}}$$
Here I decided not to stick to an $8\times8$ square; this nonsquare
set of pixel positions still ``tiles'' the plane in Escher-like fashion,
if we replicate it at 8-pixel intervals. The characters are considered
to be 8~pixels wide
and 8~pixels tall, as before, but they are no longer
confined to an $8\times8$ bounding box. The reference point is the
lower left corner of position~24.

The matrix above is actually better than the one I first came up with,
but I've forgotten what that one was. John Hobby took a look at mine
and suggested this alternative, because he wanted the pattern of
{\it black\/} pixels in character~$k$ to be essentially the same as the
pattern of {\it white\/} pixels in character $64-k$. \ (Commercial
halftone schemes start with small black dots on a white background;
then the dots grow until they form a checkerboard of black and white;
then the white dots begin to shrink into their black background.) \
The matrix above has this symmetry property, because the sum of the
entries in positions $(i,j)$ and $(i,j+4)$ is~63 for all $i$ and~$j$,
if you consider ``wraparound'' by computing indices modulo~8.

John and I used this new ordering of pixel positions to make a font
called |dot300|, analogous to |dt300|. It has the following gray levels:*
\bigskip
\ifaps\setbox8=\fi\centerline{\n=0
 \loop\vbox{\offinterlineskip
  \halign{&\hfil##\hfil\cr \ifodd\n\else\tbox\n\fi\cr
   \advance\n by`0 \dott\char\n\char\n\char\n\cr
   \advance\n by`0 \dott\char\n\char\n\char\n\cr
   \advance\n by`0 \dott\char\n\char\n\char\n\cr
   \advance\n by`0 \dott\char\n\char\n\char\n\cr
   \advance\n by`0 \dott\char\n\char\n\char\n\cr
   \advance\n by`0 \dott\char\n\char\n\char\n\cr
   \advance\n by`0 \dott\char\n\char\n\char\n\cr
   \advance\n by`0 \dott\char\n\char\n\char\n\cr}}%
 \ifnum\n<64 \advance\n by 1 \repeat}
\ifaps\setbox6=\vbox{} \ht6=\ht8 \wd6=\wd8 \dp6=\dp8 \box6 \setbox8=\null\fi
\bigskip\noindent
Now we have a pleasantly uniform gradation, except for an inevitable
anomaly between characters 62 and~63. The density reaches 50\% somewhere
around character number~45, and we can compensate for this by preprocessing
the data to be printed.
 
The three images that were displayed with |dt300| above look like this
when |dot300| is used:*
$$\vbox to 44mm{}$$ % generated by fig2.tex

My students were able to use |dot300| successfully, so I stopped working
on halftones and resumed my normal activities.

However, I realized later that |dot300| can easily be improved, because
each of its characters is made up of two dots that are about the same
size. There's no reason why the dots of a halftone image need to be paired
up in such a way. With just a bit more work, we can typeset each dot
independently!

Thus, I made a font |hf300| with just 33 characters (not 65 as before),
using the matrix
$$\def\\{\omit\hfil}\def\|{\omit\lbox}\def\_{\omit\bbox}
\vbox{\halign{&\mbox{#}\cr
\\&\\&\\&31\cr
\\&\\&19&23&27&\_&\_&\_&\_&\_\cr
\\&\\&14&7&11&15&17&\\&\\&\\&\|\cr
\\&26&10&2&3&5&21&29&\\&\\&\|\cr
30&22&6&0&1&9&25&\\&\\&\\&\|\cr
\\&18&12&8&4&13&\_&\_&\_&\_&\|\cr
\\&\\&\\&24&20&16\cr
\\&\\&\\&\\&28\cr}}$$
to control the order in which pixels are blackened. (This matrix corresponds
to just one of the two dots in the larger matrix above.) The characters
are still regarded as 8~pixels wide, but they are now only 4~pixels tall.
When a picture is typeset, the odd-numbered rows are to be offset
horizontally by 4~pixels.

Here is the \MF\ file |hf.mf| that was used to generate the single-dot font:
\beginlines
|% halftone font with 33 levels of gray, characters "0" (white) to "P" (black)|
\smallskip
|pair p[]; % the pixels in order (first p0 becomes black, then p1, etc.)|
|p0=(1,1); p4=(2,0); p8=(1,0); p12=(0,0);|
|p16=(3,-1); p20=(2,-1); p24=(1,-1); p28=(2,-2);|
|transform r; r=identity rotatedaround ((1.5,1.5),90);|
\smallbreak
|for i=0 step 4 until 28:|
| p[i+1]=p[i] transformed r;|
| p[i+3]=p[i+1] transformed r;|
| p[i+2]=p[i+3] transformed r;|
| endfor|
\smallbreak
|w#:=8/pt; % that's 8 pixels|
|font_quad:=w#; designsize:=8w#;|
\smallbreak
|picture prevchar; prevchar=nullpicture; % the pixels blackened so far|
|for i=0 upto 32:|
| beginchar(i+ASCII"0",w#,.5w#,0); currentpicture:=prevchar;|
| if i>0: addto currentpicture also unitpixel shifted p[i-1]; fi|
| prevchar:=currentpicture; endchar;|
| endfor|
\endlines
(There's also a file |hf300.mf|, analogous to the file |dt300.mf| above.)

Here's how the three example images look when they're rendered by font |hf300|:*
$$\vbox to 44mm{}$$ % generated by fig3.tex
They are somewhat blurry because they were generated second-hand from data
intended for square pixels; sharper results are possible if the data is
expressly prepared for a $45↑\circ$ grid. For example, here is a sharper Mona
Lisa, and an image
whose dots were computed directly by mathematical formulas:*
$$\vbox to 44mm{}$$ % generated by fig4.tex

The \TeX\ macros |hf65.tex| shown above must be replaced by another
set |hf33.tex| when independent dots are used:
\beginlines
|\font\halftone=hf300  % for halftones on the Imagen 300, each dot independent|
|\chardef\other=12|
\smallskip
|\newif\ifshifted|
|\def\shift{\moveright.5em}|
|\def\beginhalftone{\vbox\bgroup\offinterlineskip\halftone|
| \catcode`\.=\active\shiftedtrue\shift\hbox\bgroup}|
|{\catcode`\.=\active \gdef.{\egroup|
| \ifshifted\shiftedfalse\else\shiftedtrue\shift\fi\hbox\bgroup\ignorespaces}}|
|\def\endhalftone{\egroup\setbox0=\lastbox\egroup}|
\smallbreak
|% Example of use:|
|% \beginhalftone|
|% chars for top halfline of picture. (shifted right 4 pixels)|
|% chars for second halfline of picture. (not shifted right)|
|% chars for third halfline of picture. (shifted right 4 pixels)|
|% ...|
|% chars for bottom halfline of picture. (possibly shifted right)|
|% \endhalftone|
\endlines
These macros are much simpler than those of |hf65|, because the 33 ASCII
characters |"0"| to |"P"| have no special meaning to plain \TeX.

We can also create an analogous font |hf723| for the high-resolution APS,
in which case the pictures come out looking like this:
$$\vbox to 19mm{}$$ % generated by apsfig.tex
The same \TeX\ macros were used, but font |\halftone| was defined to be
|hf723| instead of |hf300|. Now the pictures are smaller, because the font
characters are still 8~pixels wide, and the pixels have gotten smaller.
At this resolution the halftones look ``real,'' except that they are too dark.
This problem can be fixed by adjusting the densities in a preprocessing program.
Also, small deficiencies in the APS's analog-to-digital conversion
hardware become apparent when such tiny characters are typeset.

What resolution is needed? It is traditional to measure the quality of
a halftone screen by counting the number of dots
per inch in the corresponding unrotated grid, and it's easy to do
this with a magnifying glass. 
The photographs in a newspaper like the {\sl International Herald Tribune\/}
use a 72-line screen, rotated $45↑\circ$; this is approximately
the resolution $50\sqrt2$ that we would obtain with the |hf400| font on
a laser printer with 400 dots per inch. (The 300-per-inch font |hf300| gives
a rotated screen with only $37.5\sqrt2\approx 53$ dots per inch.) The photographs
on the book jacket of {\sl Computers \& Typesetting\/} have a 133-line
screen, again rotated $45↑\circ$; this is almost identical to the resolution
of |hf723|. But this is not the upper limit:
A book that reproduces photographs with exceptionally high
quality, such as {\sl Portraits of Success\/} by Carolyn Caddes
(Portola Valley: Tioga Press, 1986), has a screen of about 270 lines per inch,
in this case rotated $30↑\circ$.
\medbreak Let's turn now to another problem: Suppose we have an image for which
we want to obtain the best possible representation on a laser printer
of medium resolution, because we will be using that image many times---for
example, in a letterhead. In such cases it is clearly desirable to
create a special font for that image alone; instead of using a
general-purpose font for halftones, we'll want to control every pixel. The
desired image can then be typeset from a special-purpose font of ``characters''
that represent rectangular subsections of the whole.

The examples above were produced on an Imagen printer as 64 lines of
55 columns per line, with 8~pixels in each line and each column.
To get an equivalent picture with every pixel selected individually, we
can make a font that has, say, 80 characters, each 64 pixels tall and
44 pixels wide. By typesetting eight rows of ten characters each, we'll
have the desired image. For example, the following picture was
done in that way:*
$$\vbox to 44mm{}$$ % generated by fig5.tex
\TeX\ will typeset such an image if we say |\monalisa| after making the
following definitions:
\beginlines
|\font\mona=mona300[hf,dek]|
\smallskip
|\newcount\m \newcount\n|
|\def\monalisa{\vbox{\mona \offinterlineskip \n=0|
| \loop \hbox{\m=0 \loop \char\n \global\advance\n by 1|
|   \advance\m by 1 \ifnum\m<10 \repeat}|
|  \ifnum\n<80 \repeat}}|
\endlines
And once we have the individual pieces, we can
combine them to get unusual effects:* % I lost the source file for these!
$$\vbox to80mm{}$$

The font |mona300| shown above was generated from a file |mona.mf|
that began like this:
\beginlines
|row(1); cols(1,5,9,13,15,17,21,24,30,32,39,46,56,62,70,|
|               78,86,95,103,110,118,120,127,135,142,151,159,167,175,183,|
|               191,198,207,215,223,230,238,246,254,263,271,279,287,295,302,|
|               311,318,328,334,342,350,358,366,367,375,382,383,390,392,398,|
|               400,405,408,414,416,421,424,430,432,439);|
|row(2); cols(4,7,12,20,23,28,30,37,38,40,45,48,53,61,64,|
\endlines
\dots\ and so on, until 512 rows had been specified. The parameter file
|mona300.mf| was
\beginlines
|% Mona Lisa for Imagen 300|
|mode_setup;|
|if (pixels_per_inch<>300) or (mag<>1):|\qquad\dots\quad%
 $\langle\,$error messages as before$\,\rangle$
|else: input picfont|
| width:=44; height:=64; m:=8; n:=10; filename:="mona";|
| do_it; fi|
|end.|
\endlines
and the driver file |picfont.mf| was
\beginlines
|def do_it=|
| for j=0 upto n-1: jj:=width*j; jjj:=jj+width; jjjj:=j;|
| scantokens("input "&filename); endfor enddef;|
|string filename;|
\smallbreak
|def row(expr x) =|
| cc:=(x-1)div height; rr:=height-1-((x-1)mod height);|
| if rr=height-1: beginchar(cc*n+jjjj,width/pt,height/pt,0); fi enddef;|
\smallbreak
|def cols(text t) =|
| for tt:=t: exitif tt>=jjj; if tt>=jj:|
|  addto currentpicture also unitpixel shifted (tt,rr); fi endfor|
| if rr=0: xoffset:=-jj; endchar; fi enddef;|
\endlines
This is not very efficient, but it's interesting and it seems to work.

\eject
\message{Now say "tex end" to get the rest!}
\bye % Have to restart TeX and let it partition its memory differently